"""
72.编辑距离
https://leetcode-cn.com/problems/edit-distance

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符

示例:
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

提示:
0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成
"""

class Solution:
  """
  设:
    x = 已编辑的次数
    m = 还需要匹配的word1子串长度
    n = 还需要匹配的word2子串长度
  则
    `minDistance(word1, word2) == x + min(distances(word1[:m], word2[:n]))`
    其中: 
      distances = [
        n #(当 m == 0 时),
        m #(当 n == 0 时),
        minDistances(word1[:m-1], word2[:n-1])  #(当 word1[m-1] == word2[n-1] 时),

        minDistances(word1[:m], word2[:n-1]) + 1  #(插入操作),
        minDistances(word1[:m-1], word2[n]) + 1  #(删除操作),
        minDistances(word1[:m-1], word2[:n-1]) + 1 #(替换操作)
      ]
  """
  def minDistance(self, word1: str, word2: str) -> int:
    m = len(word1)
    n = len(word2)
    # 创建dp表，缓存 minDistance(word1[:m+1], word2[:n+1]) 的值
    dp = [[0] * (n+1) for _ in range(m+1) ]
    # 设置 m == 0 时 的dp表状态
    for i in range(n+1):
      dp[0][i] = i
    # 设置 n == 0 时 的dp表状态
    for i in range(m+1):
      dp[i][0] = i
    # 动态规划
    for i in range(1, m+1):
      for j in range(1, n+1):
        if word1[i-1] == word2[j-1]:
          dp[i][j] = dp[i-1][j-1]
        else:
          dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1
    return dp[m][n]
